package algorithm.leetcode.I1to100;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 整体也是一个枚举+剪枝的过程
 * 个人认为回溯有三类: 排列+剪枝(使用useMaker标记尝试过的)  组合+剪枝(用startFromWhere标记从哪开始搜索)  枚举+剪枝
 * 这份代码除了isValidSudoku方法不是我自己写的,其他都是我自己一点点debug出来的
 */

public class Q37 {

    /**
     * 注意返回值是void,这个有点费事
     * @param board 待解数独
     */
    public void solveSudoku(char[][] board) {
        // 存放所有可能的解
        List<char[][]> result = new LinkedList<>();

        // 调用核心回溯方法,从第1个格子开始填
        backTrack(result, board, 0);

        // 为了配合返回void必须在不修改board引用的情况下改变内部的值
        // 注意题目已经确保解唯一,若不唯一可从result获取全部
        for (int i = 0; i < board.length; i++) {
            board[i] = result.get(0)[i];
        }
    }

    /**
     * 深拷贝二维数组
     * @param origin 原始二维数组
     * @return 深拷贝后的二维数组
     */
    public char[][] deepCopy(char[][] origin) {
        char[][] res = new char[origin.length][];
        for (int i = 0; i < origin.length; i++) res[i] = origin[i].clone();
        return res;
    }


    /**
     * 回溯核心方法
     * @param result 全局解
     * @param board 当前解
     * @param tryPosition 待尝试的位置
     */
    private void backTrack(List<char[][]> result,
                           char[][] board,
                           int tryPosition) {
        // 如果不符合,直接剪枝
        if (!isValidSudoku(board)) return;
        // 上面已经判断过一次是否满足了,下面的肯定都合法,省略一次判断,返回
        else if (tryPosition == 81) {
            result.add(deepCopy(board));
            return;
        }

        // 向后探索,绝对不能写成下面注释的样子,会造成重复解
        int row = tryPosition / 9;
        int col = tryPosition % 9;
        if (board[row][col] == '.') {
            for (int k = 0; k < 9; k++) {
                board[row][col] = (char) (k + 49); // '1'的ASCII码是49
                backTrack(result, board, tryPosition+1);
                board[row][col] = '.';
            }
        }
        // 注意这个地方,如果tryPosition的位置有数字了,直接按游戏展开树纵向深入,比上面的IF分支去掉了尝试和回溯的部分
        // 可以理解为有障碍的排列
        else {
            backTrack(result, board, tryPosition+1);
        }
        // for (int i = 0; i < board.length; i++) {
        //     for (int j = 0; j < board[0].length; j++) {
        //         // 如果这个位置没填,尝试
        //         if (board[i][j] == '.') {
        //             for (int k = 0; k < 9; k++) {
        //                 board[i][j] = (char) (k + 49);
        //                 backTrack(result, board, vaccineCell-1);
        //                 // if (i != 8 || j != 8 || k != 8) board[i][j] = '.';
        //                 board[i][j] = '.';
        //             }
        //         }
        //     }
        // }

    }

    // 这个方法的说明可以看Q36
    private boolean isValidSudoku(char[][] board) {
        int[][] rows = new int[9][9];
        int[][] col = new int[9][9];
        int[][] diag = new int[9][9];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '1';
                    int index_box = (i / 3) * 3 + j / 3;

                    // 这个判重逻辑是:第i个行/列/小数组的数字应该填在rows/col/diag的第i行的对应数字这个位置
                    // 如果这个位置之前填过了(用1标识)说明重复了,直接返回false
                    // 如果这个位置之前没填过(按这个代码数组是用0初始化的)把这个位置填1
                    if (rows[i][num] == 1) return false;
                    else rows[i][num] = 1;

                    if (col[j][num] == 1) return false;
                    else col[j][num] = 1;

                    if (diag[index_box][num] == 1) return false;
                    else diag[index_box][num] = 1;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        char[][] board = {{'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {'.', '.', '.', '.', '8', '.', '.', '7', '9'}};

        // char[][] board = {{'5','3','4','6','7','8','9','1','2'},
        //         {'6','7','2','1','9','5','3','4','8'},
        //         {'1','9','8','3','4','2','5','6','7'},
        //         {'8','5','9','7','6','1','4','2','3'},
        //         {'4','2','6','8','5','3','7','9','1'},
        //         {'7','1','3','9','2','4','8','5','6'},
        //         {'9','6','1','5','3','7','2','8','4'},
        //         {'2','8','7','4','1','9','6','3','5'},
        //         {'3','4','5','2','8','6','.','.','.'}};

        Q37 q37 = new Q37();

        q37.solveSudoku(board);

        System.out.println("==========================");
        for (char[] chars : board) {
            System.out.println(Arrays.toString(chars));
        }
    }
}
